package 二叉树;

public class No450删除二叉搜索树中的节点 {

    /**
     * 给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
     *
     * 一般来说，删除节点可分为两个步骤：
     *
     * 首先找到需要删除的节点；
     * 如果找到了，删除它。
     * 说明： 要求算法时间复杂度为 O(h)，h 为树的高度。
     */

    public TreeNode deleteNode(TreeNode root, int key) {
        return dg(root,key);
    }

    private TreeNode dg(TreeNode node,int key){
        //删除了之后如何保持平衡?
        /**
         * 删除时有三种情况:1.左子树为空2.右子树为空3.左右子树都存在
         * 12好办,难办的是3
         * 方法一:在左子树中找到最大节点,上提
         * 方法二:在右子树中找到最小节点,上提
         * 这里我们选用找到左子树中的最大节点
         */
        if(node==null)
            return null;
        if(node.val>key){
            node.left=dg(node.left,key);
            return node;
        }
        if(node.val<key){
            node.right=dg(node.right,key);
            return node;
        }
        //找到当前的节点了
        //情况1
        if(node.left==null){
            TreeNode temp=node.right;
            node.right=null;//脱离当前树
            return temp;//返回
        }
        //情况2
        if(node.right==null){
            TreeNode temp=node.left;
            node.left=null;//脱离当前树
            return temp;//返回
        }
        //情况3,找到左子树的最大节点
        TreeNode resultLeft = removeMax2(node.left);
        MaxNode.right=node.right;
        MaxNode.left=resultLeft;
        node.right=null;
        node.left=null;
        return MaxNode;
    }

    /**
     * 其实这里可以拆分两个方法,一:找到最小 二:删除最小
     * 然后就可不用成员变量
     */
    private TreeNode MaxNode;

    private TreeNode removeMax2(TreeNode node){
        if(node.right!=null){
            node.right=removeMax2(node.right);
            return node;
        }else{
            MaxNode=node;
            if(node.left!=null){
                TreeNode temp=node.left;
                node.left=null;
                return temp;
            }
            return null;
        }
    }

    /**
     *      5
     *   3      6
     * 2  4 null  7
     */
    public static void main(String[] args) {
        TreeNode nodeByArr = TreeNode.getNodeByArr(new Integer[]{5,3,6,2,4,null,7});
        No450删除二叉搜索树中的节点 n=new No450删除二叉搜索树中的节点();
        TreeNode treeNode = n.deleteNode(nodeByArr,3);
        treeNode.printNode();
    }

}
